//#define _CRT_SECURE_NO_WARNINGS 1
//#include <iostream>
//#include<vector>
//
//using namespace std;
//
//
//void gulosort(vector<int>& vv)
//{
//	int n = vv.size();
//	if (n < 2) return;
//	while (n >= 0)
//	{
//		for (int i = 1; i < n; i++)
//		{
//			if (vv[i - 1] > vv[i])
//			{
//				swap(vv[i], vv[i - 1]);
//			}
//		}
//		n--;
//	}
//}
//
//void select_sort(vector<int>& vv)
//{
//	int n = vv.size();
//	if (n < 2) return;
//	
//	for (int i = 0; i < n; i++)
//	{
//		int minpos = i;
//		for (int j = i + 1; j < n; j++)
//		{
//			if (vv[minpos] > vv[j])
//			{
//				minpos = j;
//			}
//		}
//		swap(vv[minpos], vv[i]);
//	}
//}
//
//void insert_sort(vector<int>& vv)
//{
//	int n = vv.size();
//	if (n < 2) return;
//
//	for (int i = 1; i < n; i++)
//	{
//		if (vv[i - 1] > vv[i])
//		{
//			int num = vv[i];
//			int j = i - 1;
//			while (j >= 0)
//			{
//				if (vv[j] > num)
//				{
//					vv[j + 1] = vv[j];
//					j--;
//				}
//				else {
//					break;
//				}
//			}
//			vv[j + 1] = num;
//		}
//	}
//}
//
//void xier_sort(vector<int>& vv)
//{
//	int n = vv.size();
//	if (n < 2) return;
//	int gap = n;
//	while (gap > 1)
//	{
//		gap /= 2;
//		for (int i = gap; i < n; i++)
//		{
//			if (vv[i - gap] > vv[i])
//			{
//				int num = vv[i];
//				int j = i - gap;
//				while (j >= 0)
//				{
//					if (vv[j] > num)
//					{
//						vv[j + gap] = vv[j];
//						j -= gap;
//					}
//					else {
//						break;
//					}
//				}
//				vv[j + gap] = num;
//			}
//		}
//	}
//}
//
//void adjustdown(vector<int>& vv, int n, int root)
//{
//	int parent = root;
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		if (child + 1 < n && vv[child + 1] > vv[child])
//		{
//			child++;
//		}
//		if (child < n && vv[parent] < vv[child])
//		{
//			swap(vv[child], vv[parent]);
//		}
//		else {
//			break;
//		}
//		parent = child;
//		child = parent * 2 + 1;
//	}
//}
//
//void heap_sort(vector<int>& vv)
//{
//	int n = vv.size();
//	if (n < 2) return;
//	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		adjustdown(vv, n, i);
//	}
//	for (int i = n - 1; i > 0; i--)
//	{
//		swap(vv[i], vv[0]);
//		adjustdown(vv, i, 0);
//	}
//}
//
//void fast_sort(vector<int>& vv, int left, int right)
//{
//	if (left >= right) return;
//	int begin = left, end = right;
//	int key = begin;
//	while (begin < end)
//	{
//		while (begin < end && vv[begin] < vv[key])
//		{
//			begin++;
//		}
//		while (begin < end && vv[end] > vv[key])
//		{
//			end--;
//		}
//		swap(vv[begin], vv[end]);
//	}
//	swap(vv[key], vv[begin]);
//	fast_sort(vv, left, begin);
//	fast_sort(vv, begin + 1, right);
//}
//
//void _mergesort(vector<int>& vv, int left, int right, vector<int>& v)
//{
//	if (left >= right) return;
//	int mid = (left + right) / 2;
//	_mergesort(vv, left, mid, v);
//	_mergesort(vv, mid + 1, right, v);
//
//	int begin1 = left, end1 = mid;
//	int begin2 = mid + 1, end2 = right;
//	int i = begin1;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (vv[begin1] < vv[begin2])
//		{
//			v[i++] = vv[begin1++];
//		}
//		else {
//			v[i++] = vv[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		v[i++] = vv[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		v[i++] = vv[begin2++];
//	}
//	for (int j = left; j <= right; j++)
//	{
//		vv[j] = v[j];
//	}
//}
//
//void mergesort(vector<int>& vv)
//{
//	int n = vv.size();
//	if (n < 2) return;
//	vector<int> v(n);
//	_mergesort(vv, 0, n - 1, v);
//}
//int main()
//{
//	vector<int> vv = { 4, 6, 5, 32, 21, 8, 37, 3 };
//	//gulosort(vv);
//	//select_sort(vv);
//	//insert_sort(vv);
//	//xier_sort(vv);
//	//heap_sort(vv);
//	//fast_sort(vv, 0, 7);
//	mergesort(vv);
//	for (auto& num : vv)
//	{
//		cout << num << " ";
//	}
//	cout << endl;
//	return 0;
//}